/**
编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:  

1 是丑数。
n 不超过1690。

思路：
不难发现生成丑数的规律：如果已知丑数ugly，那么ugly * 2，ugly * 3和ugly * 5也都是丑数。
既然求第n小的丑数，可以采用最小堆来解决。每次弹出堆中最小的丑数，然后检查它分别乘以2、3和 5后的数是否生成过，如果是第一次生成，那么就放入堆中。第n个弹出的数即为第n小的丑数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ugly-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

class Solution {
public:
    int nthUglyNumber(int n) {       
        priority_queue <long,vector<long>,greater<long>> heap;
        heap.push(1L);

        set<long> seen;
        seen.insert(1L);
        
        vector<int> factors({2,3,5});

        long currUgly = 1L, newUgly;

        for (int i = 0; i < n; ++i) {
            currUgly = heap.top();
            heap.pop();
            for(int &f: factors) {
                newUgly = currUgly * f;
                if (seen.count(newUgly) == 0) {
                    seen.insert(newUgly);
                    heap.push(newUgly);
                }
            }
        }
        return (int)currUgly;
    }
};
